1. Field of the Invention
The present invention relates generally to the field of computer systems, and more particularly to a method of instruction scheduling in superscalar or very large instruction word (VLIW) processors that reduces the harmful effects of compensation code.
2. Description of the Related Art
In a typical computer system, the central processing unit ("CPU") executes a compiler program whose job is to translate a computer program from one language into another. Typically the program to be compiled, called the source code program, is written in one of the traditional programming languages such as Pascal, FORTRAN, or C, although it may take other forms. The language into which the source code program is to be translated, called the target language, could be another programming language, object code, or code readable by a machine, for example. In any event, the compiler translates the source code program into the target language of choice.
The final step in the compiler's translation of the source code program is code generation, during which the compiler creates the final representation of the source code program in the target language. One step that is performed during the code generation process is called instruction scheduling. During instruction scheduling, individual instructions of the target code (or instructions of an intermediate representation of the target code) are rescheduled so that more instructions execute in each clock cycle, enabling faster execution of the target code instructions and more efficient use of machine resources.
Conceptually, instruction scheduling involves movement of instructions within a control flow graph representation of the program to be executed. A control flow graph is an interconnected set of basic blocks, where each basic block is simply a collection of the program's instructions. More specifically, a basic block is a series of instructions that always execute consecutively, with no possibility of halting or conditional branching under normal execution (basic blocks may or may not include procedure calls and unconditional branches, depending on how a basic block is defined by the compiler). Program control always enters a basic block from the top, i.e., the first instruction in the basic block is always the first to be executed. Therefore, once program control flows to the first instruction in a basic block, all instructions in the basic block will execute consecutively, at which point control will flow to another basic block. Because every instruction in the program is included in a basic block, the program may be entirely represented as a collection of basic blocks, interconnected by edges to reflect how program control can flow from block to block. This interconnected collection of basic blocks is the control flow diagram. Older instruction scheduling methods reorganized instructions within basic blocks to produce more efficient target code, but did not move instructions between basic blocks. In more recently developed scheduling methods, instructions are moved between blocks within a region to further increase the efficient use of machine resources. In all of these methods, instructions are scheduled into only one block at a time.
Movement of instructions between blocks creates the problem that a moved instruction might never be executed in instances when it should have been executed. For instance, referring to the sample control flow graph of FIG. 1, suppose there is a basic block B, and that program control may flow to block B from one of two predecessor blocks, P1 and P2 (in this context, a predecessor/successor block is a block immediately preceding/succeeding the block in question in the control flow diagram). Suppose further that an instruction from block B is moved upward into block P1 by the instruction scheduler. If program control flowed to block B from block P2, the instruction would never be executed. In this situation, the use of compensation code is necessary. The instruction scheduler creates compensation copies of moved instructions to guarantee that all instructions are executed as they should be, regardless of how program control proceeds. In this example, if an instruction were moved from block B to block P1 by the instruction scheduler, a compensation copy of the instruction would be placed into P2, so that the instruction will be executed no matter which path the program control takes. Compensation code is necessary any time an instruction is moved (scheduled) into a new basic block in the control flow graph, but as a result of its new location, the instruction might never be executed when it should be. The need for compensation code can also be encountered in cases of downward code motion, when an instruction is moved below a block in the control flow diagram with multiple successors.
The creation of compensation code can reduce the efficiency of target code, by increasing the number of clock cycles necessary to execute a particular block of code. Under current scheduling methods, the instructions are scheduled without heed to the effect of compensation code on the block into which it is inserted. The creation of compensation copies can therefore work against the compiler's otherwise meticulous attention to the efficient scheduling of instructions into blocks. As a result, the overall efficiency of the target code can be lowered.
The present invention is directed to overcoming, or at least reducing the effects of, the problem set forth above.